﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
//51. N 皇后
//简单分析一下，每一行就一个位置
//每一列也就一个
class Sol51
{

    IList<IList<string>> res = new List<IList<string>>();
    public IList<IList<string>> SolveNQueens(int n)
    {
        //初始化
        char[][]  path = new char[n][];
        for (int i = 0; i < n; i++)
        {
            path[i] = new char[n];
            for (int j = 0; j < n; j++)
            {
                path[i][j] = '.';
            }
        }
      


        bool[] used = new bool[n];
        int row = 0;//第几行
        DFS(n, used, row, path);
        
        return res;
    }

    private void DFS(int n, bool[] used,int row, char[][] path)
    {
        //停止条件
        if(row==n)
        {
            //收集结果

            //path转换成一个字符串
           res.Add( pathToStr(path));
            return;
        }
       

        for (int i = 0; i < n; i++)//当前层只能存一个
        {
            
            if (isvalid(path,i,row,n))//使用过的不可以使用
            {
                
                path[row][i] = 'Q';
                //Console.WriteLine(res[row][i]);
                
                DFS(n, used, row + 1, path);
                //回溯
               
                path[row][i] = '.';//还没有记录就把值给改了

                //continue;//不可以跳过本层，不然补充的.输入不了

            }
            //还有一种情况没有考虑。斜着的，所有要间隔两个



            

        }
    }

    private bool isvalid(char[][] path, int col, int row, int n)
    {

        //检测同一列
        for(int i = 0;i < row; i++) {
            if (path[i][col] == 'Q') {
                return false;
            }
        }
        //检测当前的左上角,包括整个直线

        for (int i = 0; i < row; i++)//行数
        {

            int j= col-row+i;
            if(j>=0)
            {
                if (path[i][j] == 'Q')
                {
                    return false;
                }
            }


        }


        //检测当前的右上角
        for (int i = 0; i < row; i++)//行数
        {

            int j = col +row -i;
            if (j < n)
            {
                if (path[i][j] == 'Q')
                {
                    return false;
                }
            }


        }
return true;
    }

    private IList<string> pathToStr(char[][] path)//这个操作有点多余,不多余，string不能像数组一样操作
    {
        IList<string> res =new List<string>();
        for (int i = 0;i<path.Length ; i++)//遍历每一行
        {
            string rowStr = null;

            for(int j = 0; j < path[i].Length ; j++)
            {
                rowStr += path[i][j];
            }
            //收集
            res.Add(rowStr);
        }
        return res;

    }
}

class Program51
{
    static void Main51(string[] args)
    {

        Sol51 sol = new Sol51();
        IList<IList<string>>  res = sol.SolveNQueens(4);
        Console.WriteLine("几种情况：" +res.Count);
        for (int i = 0; i < res.Count; i++)
        {
            for (int j = 0; j < res[i].Count; j++)
            {
                Console.WriteLine(res[i][j]) ;
            }
            Console.WriteLine("___________");
        }
    }
}
